//先用乘法运算，快速到达target
//如果正好是target，直接返回
//否则有两个目标值：比target大的一个数，和比target小的一个数，与target作差来得到更小的问题
//如果得到的新target比原先的target更大，可能会导致重复递归导致栈溢出，所以直接不考虑
import java.util.HashMap;
import java.util.Map;

public class Solution964 {

    Map<Integer,Integer> map=new HashMap<>();

    public int leastOpsExpressTarget(int x, int target) {
        if (!map.containsKey(target)){
            if (target<x){
                map.put(target,Math.min(2*target-1,2*(x-target)));
            }else{
                long t=x;
                int m=0;
                while (t<target){
                    t=t*x;
                    m++;
                }
                if (t==target){
                    map.put(target,m);
                }else{
                    int l;
                    if (t-target>=target){
                        l=m+leastOpsExpressTarget(x,(int)(target-t/x));
                    }else{
                        l=Math.min(m+1+leastOpsExpressTarget(x,(int)(t-target)),m+leastOpsExpressTarget(x,(int)(target-t/x)));
                    }
                    map.put(target,l);
                }
            }
        }
        return map.get(target);
    }

    public static void main(String[] args) {
        System.out.println(new Solution964().leastOpsExpressTarget(3,365));
    }
}
